package com.chj.jz.dp.class02;

import java.util.Arrays;

//https://www.lintcode.com/problem/counting-bits/description
public class Code10_CountingBits {

	/**
	 * @param num:
	 *            a non negative integer number
	 * @return: an array represent the number of 1's in their binary
	 */
	public static int[] countBits(int num) {
		// write your code here
		int[] f = new int[num + 1];
		int i;
		f[0] = 0;
		for (i = 1; i <= num; i++) {
			// f[i] = (i % 2) + f[i / 2];
			f[i] = (i & 1) + f[i >> 1];
		}

		return f;
	}

	public static void main(String[] args) {
		{
			System.out.println(170 & 15);
			System.out.println(170 | 15);
			System.out.println(170 ^ 15);
			System.out.println(~15);
			System.out.println(~37);
			System.out.println(16 >> 3);
			System.out.println(16 << 3);
			System.out.println(15 % 2);
			System.out.println(14 % 2);
			System.out.println(15 & 1);
			System.out.println(14 & 1);
		}
		{
			System.out.println(Arrays.asList(countBits(5)));
			System.out.println(Arrays.asList(countBits(3)));
		}
		{
			// int[][] arr = new int[][] { { 1, 3, 2 } };
			// System.out.println(minPathSum(arr));
		}
	}

}
